package com.cuz.daileetcode.bat100;

import java.util.Comparator;
import java.util.PriorityQueue;

public class 二维接雨水 {
    public static void main(String[] args) {
        //[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]
        //[[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]]
        int[][] ints = {
                {12, 13, 1, 12},
                {13, 4, 13, 12},
                {13, 8, 10, 12},
                {12, 13, 12, 12},
                {13, 13, 13, 13},
        };
        System.out.println(solution1(ints));
    }

    static class N {
        int value;
        int x;
        int y;

        public N(int value, int x, int y) {
            this.value = value;
            this.x = x;
            this.y = y;
        }
    }

    public static int solution1(int[][] heightMap) {
        if (heightMap == null || heightMap.length < 3 || heightMap[0].length < 3) {
            return 0;
        }
        PriorityQueue<N> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.value));
        int rowMax = heightMap.length;
        int colMax = heightMap[0].length;
        boolean[][] hasUsed = new boolean[rowMax][colMax];
        //初始化第1列 和最后一列，因为这两列是不可能容纳水的
        for (int i = 0; i < rowMax; i++) {
            heap.add(new N(heightMap[i][0], i, 0));
            heap.add(new N(heightMap[i][colMax - 1], i, colMax - 1));
            hasUsed[i][0] = true;
            hasUsed[i][colMax - 1] = true;
        }
        //处理第一行 和最后一行 这里排除了四个边角，因为上面的if以及将他们加入堆了
        for (int i = 1; i < colMax - 1; i++) {
            heap.add(new N(heightMap[0][i], 0, i));
            heap.add(new N(heightMap[rowMax - 1][i], rowMax - 1, i));
            hasUsed[0][i] = true;
            hasUsed[rowMax - 1][i] = true;
        }
        //结果
        int ans = 0;
        //当前最高的点，也就是当前的瓶颈
        int curMaxHeight = Integer.MIN_VALUE;
        while (!heap.isEmpty()) {
            //当前最洼地
            N min = heap.poll();
            //能否推高 瓶颈，这一步意味着 这个洼地的上下左右承载水是一俩于当前位置
            //还是依赖于之前的高点
            curMaxHeight = Math.max(curMaxHeight, min.value);
            int x = min.x;
            int y = min.y;
            //前后左右 from 处理了越界和 hasUsed的更新
            int right = from(heightMap, hasUsed, x + 1, y);
            int left = from(heightMap, hasUsed, x - 1, y);
            int top = from(heightMap, hasUsed, x, y - 1);
            int down = from(heightMap, hasUsed, x, y + 1);
            if (right != Integer.MIN_VALUE) {
                //结算水量
                ans += Math.max(0, curMaxHeight - right);
                //进入堆
                heap.add(new N(heightMap[x + 1][y], x + 1, y));
            }
            if (left != Integer.MIN_VALUE) {
                ans += Math.max(0, curMaxHeight - left);
                heap.add(new N(heightMap[x - 1][y], x - 1, y));
            }
            if (top != Integer.MIN_VALUE) {
                ans += Math.max(0, curMaxHeight - top);
                heap.add(new N(heightMap[x][y - 1], x, y - 1));
            }
            if (down != Integer.MIN_VALUE) {
                ans += Math.max(0, curMaxHeight - down);
                heap.add(new N(heightMap[x][y + 1], x, y + 1));
            }
        }
        return ans;
    }


    private static int from(int[][] height, boolean[][] hasUse, int x, int y) {
        if (x < 0 || x >= height.length || y < 0 || y >= height[0].length || hasUse[x][y]) {
            return Integer.MIN_VALUE;
        }
        hasUse[x][y] = true;
        return height[x][y];
    }
}
